home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / answrbok / 4_6.lha / 4_6 / 4_6b.c < prev    next >
Text File  |  1993-08-08  |  2KB  |  106 lines
  1. * Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
  2. * The C++ Answer Book */
  3. * Tony Hansen */
  4. * All rights reserved. */
  5. / quick sort
  6. / Version 2
  7. / Based on "Algorithms" by Robert Sedgewick
  8. / Chapter 9, pp 103-113
  9.  
  10. include <swap.h>
  11.  
  12. / Global variables
  13. tatic int *a;
  14. onst int cutoff = 16;
  15.  
  16. / insertion sort to finish the job off
  17. tatic void inssort(int left, int right)
  18.  
  19.    for (int i = left + 1; i <= right; i++)
  20. {
  21. int v = a[i];
  22.  
  23. for (int j = i, k = j-1;
  24.      j > 0 && a[k] > v;
  25.      j--, k--)
  26.     a[j] = a[k];
  27.  
  28. a[j] = v;
  29. }
  30.  
  31.  
  32. / partition the array into two halves
  33. / after the partition,
  34. / K[left] < ... < K[i] < ... < K[right]
  35. / iqsort will then recursively sort
  36. / K[left] through K[i-1] and
  37. / K[i+1] through K[right]
  38. tatic int partition(int left, int right)
  39.  
  40.    // sort-three: sort left, middle and right elements
  41.    // to find the partitioning element
  42.    int mid = (left + right) / 2;
  43.  
  44.    if (a[left] > a[mid])
  45. swap(a[left], a[mid]);
  46.  
  47.    if (a[left] > a[right])
  48. swap(a[left], a[right]);
  49.  
  50.    if (a[mid] > a[right])
  51. swap(a[mid], a[right]);
  52.  
  53.    // move the partitioning element
  54.    // to the right end
  55.    int j = right - 1;
  56.    swap(a[mid], a[j]);
  57.    int i = left;
  58.    int v = a[j];
  59.  
  60.    do  {
  61. do  {
  62.     i++;
  63. } while (a[i] < v);
  64.  
  65. do  {
  66.     j--;
  67. } while (a[j] > v);
  68.  
  69. swap(a[i], a[j]);
  70.    } while (i < j);
  71.  
  72.    swap(a[j], a[i]);
  73.    swap(a[i], a[right-1]);
  74.    return i;
  75.  
  76.  
  77. / the secondary routine which will
  78. / do the actual sorting
  79. tatic void iqsort(int left, int right)
  80.  
  81.    while (right - left > cutoff)
  82. {
  83. int i = partition(left, right);
  84.  
  85. if (i - left > right - i)
  86.     {
  87.     iqsort(i+1, right);
  88.     right = i - 1;
  89.     }
  90.  
  91. else
  92.     {
  93.     iqsort(left, i-1);
  94.     left = i + 1;
  95.     }
  96. }
  97.  
  98.  
  99. oid qsort2(void *array, unsigned nel,
  100.     unsigned, int (*)(const void*,const void*))
  101.  
  102.    a = (int*)array;        // set global pointer
  103.    iqsort(0, nel-1);
  104.    inssort(0, nel-1);
  105.  
  106.